package compile;

import java.util.*;

/**
 * 第一次实验：NFA->DFA
 */
public class SubsetConstruction {
    /** 黎旭 */
    /** 存放dfa的转移函数
     * 一个等价类就是一个Map集合
     * 键为输入符号(转换函数)
     * 值为下一个状态的集合 */
    private Map<Set<Integer>, Map<Character, Set<Integer>>> dfa;
    /**
     * 存储DFA状态集合和状态编号的映射关系
     * 键为新的等价类
     * 值为重命名的等价类*/
    private Map<Set<Integer>, Integer> stateMap;
    /** 记录DFA的状态的个数 */
    private int stateCount;

    /**
     * 子集构造算法
     * @param nfa
     */
    public SubsetConstruction(Map<Integer, Map<Character, Set<Integer>>> nfa) {
        /** 初始化dfa */
        dfa = new HashMap<>();
        /** 初始化映射状态 */
        stateMap = new HashMap<>();
        /** 初始为0 */
        stateCount = 0;

        /** 计算NFA的起始状态的等价类
         *  假设起始状态为 0 */
        Set<Integer> startState = epsilonClosure(Set.of(0), nfa);
        System.out.println("起始状态集合"+startState);

        /** 起始状态添加到 DFA集合中 并且同步映射关系加一 */
        stateMap.put(startState, stateCount++);
        /** 构造队列（先进先出，满足广度优先的遍历特点），采用广度优先去搜索 */
        Queue<Set<Integer>> queue = new LinkedList<>();
        queue.offer(startState);


        /** 使用广度优先搜索算法构造DFA
         *  曹靓丽 */
        while (!queue.isEmpty()) {
            /** //取出一个DFA状态状态集合 */
            Set<Integer> currState = queue.poll();
            Map<Character, Set<Integer>> transitions = new HashMap<>();//存储DFA的状态转移函数
            for (int state : currState) {//遍历DFA状态中的所有DFA状态
                System.out.println(queue+"   "+state);
                /** 为什么可能为空 */
                if(nfa.get(state)==null){
                    continue;
                }
                System.out.println(state+" 发出的所有 弧(转移符号) "+nfa.get(state).keySet());
                /** //遍历该NFA状态的所有转移符号 */
                for (Character symbol : nfa.get(state).keySet()) {
                    /** 如果转移符号不是 * (*代表空)  */
                    if (symbol != '*') {
                        /** 计算转移符号对应的NFA状态的等价类 */
                        Set<Integer> nextState = epsilonClosure(nfa.get(state).get(symbol), nfa);
                        System.out.println("状态"+state+"通过转换符号"+symbol+"到达的下一个状态集合"+nextState);
                        // 将转移符号和等价类加入DFA状态的转移函数
                        /** 这里其实就是临时保存结果   */
                        transitions.computeIfAbsent(symbol, k -> new HashSet<>()).addAll(nextState);
                        System.out.println("状态转移函数:"+transitions);
                    }
                }
            }

            //遍历DFA状态的转移函数中的所有等价类
            /** 将计算得出的结果保存到dfa中， */
            for (Set<Integer> nextState : transitions.values()) {
                if (!stateMap.containsKey(nextState)) {
                    stateMap.put(nextState, stateCount++);
                    queue.offer(nextState);
                }
            }
            System.out.println("保存结果 "+currState+"   "+transitions);
            /** 对应构造出来的表格的一行 */
            dfa.put(currState, transitions);
        }
    }

    /**
     * 计算状态集合经过states转移符号的后续状态集合（等价类）
     * 陈佳
     * */
    private Set<Integer> epsilonClosure(Set<Integer> states, Map<Integer, Map<Character, Set<Integer>>> nfa) {
        //初始化后续状态集合为状态集合本身
        Set<Integer> closure = new HashSet<>(states);
        //后进先出栈
        Stack<Integer> stack = new Stack<>();
        stack.addAll(states);

        while (!stack.isEmpty()) {
            //从栈中取出一个状态
            int state = stack.pop();
            /** 这里使用getOrDefault替代get，即当值为空时采用默认值替代，避免出现null异常
             * 这一步的作用是去寻找此状态是否可以通过 * 到达新的状态 ，将这些状态加入到（后续状态集合）等价类中*/
            for (int nextState : nfa.getOrDefault(state, Collections.emptyMap()).getOrDefault('*', Collections.emptySet())) {
                /**
                 * 在这里判断它是不是一个新的状态，是的话就加入到closure中，并添加到栈中从此状态继续寻找是否还能通过 * 到达后续状态*/
                if (closure.add(nextState)) {
                    stack.push(nextState);
                }
            }
        }
        /**
         * 最终栈为空说明找到此状态集合states的 等价类  */
        return closure;
    }

    public Map<Set<Integer>, Map<Character, Set<Integer>>> getDFA() {
        return dfa;
    }

    public Map<Set<Integer>, Integer> getStateMap() {
        return stateMap;
    }

    /** 坛子一 */
    public static void main(String[] args) {
        Map<Integer, Map<Character, Set<Integer>>> nfa = new HashMap<>();

        //模拟用户输入
        //输入的含义 状态0 可以通过 转换符号 *(代表空) 得到后续状态集合[1,2]，通过转换符号 a 可以得到后续状态集合[1,3];
        nfa.put(0, Map.of('*',Set.of(5)));
        nfa.put(5,Map.of('*',Set.of(1),'a',Set.of(5),'b',Set.of(5)));
        nfa.put(1, Map.of('a', Set.of(3),'b', Set.of(4)));
        nfa.put(3, Map.of('a', Set.of(2)));
        nfa.put(4, Map.of('b', Set.of(2)));
        nfa.put(2, Map.of('*', Set.of(6)));
        nfa.put(6,Map.of('*',Set.of(100),'a',Set.of(6),'b',Set.of(6)));

        //
        SubsetConstruction sc = new SubsetConstruction(nfa);
        Map<Set<Integer>, Map<Character, Set<Integer>>> dfa = sc.getDFA();
        Map<Set<Integer>, Integer> stateMap = sc.getStateMap();

        System.out.println("DFA:");
        for (Set<Integer> state : dfa.keySet()) {
            System.out.print(stateMap.get(state) + ": ");
            for (char symbol : dfa.get(state).keySet()) {
                System.out.print(symbol + "->" + stateMap.get(dfa.get(state).get(symbol)) + " ");
            }
            System.out.println();
        }
    }
}
